#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 计算二叉树的最大宽度
int maxWidth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }

    queue<pair<TreeNode*, int>> q;
    q.push({root, 0});
    int maxWidth = 0;

    while (!q.empty()) {
        int levelSize = q.size();
        int startIdx = q.front().second;
        int endIdx = q.back().second;
        maxWidth = max(maxWidth, endIdx - startIdx + 1);

        for (int i = 0; i < levelSize; i++) {
            auto curr = q.front();
            q.pop();
            if (curr.first->left) {
                q.push({curr.first->left, 2 * curr.second});
            }
            if (curr.first->right) {
                q.push({curr.first->right, 2 * curr.second + 1});
            }
        }
    }
    return maxWidth;
}

int main() {
    // 创建一棵二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->right->right = new TreeNode(9);

    // 计算二叉树的最大宽度
    int width = maxWidth(root);
    cout << "Maximum width of the Binary Tree: " << width << endl;

    return 0;
}
